 //437.路径总和III
 //https://leetcode.cn/problems/path-sum-iii/
class Solution {
    int dfs(TreeNode* root, long sum)
    {
        //这里需要注意sum为long 否则溢出
        if(root == nullptr) return 0;
        int ret = 0;
        //如果当前节点与sum相同(即相减后为0) 则该路径可以组成targetSum
        if(root->val == sum) ++ret;
        //继续遍历查找是否还有
        ret += dfs(root->left, sum - root->val);
        ret += dfs(root->right,sum - root->val);
        return ret;
    }
public:
    int pathSum(TreeNode* root, int targetSum) {
        if(root == nullptr) return 0;
        //以当前节点为根节点遍历查找
        int ret = dfs(root,targetSum);
        //以左右节点为根节点查找
        ret += pathSum(root->left,targetSum);
        ret += pathSum(root->right,targetSum);
        return ret;
    }
};